Information in databases may be organized according to any number of techniques. Examples of the many database indexes include the quadtree, the B−tree, and the R−tree. Different database index structures may be more suitable for particular types of data. For example, some database index structures, such as B+trees, may not be suited multi-dimensional data.
The R−tree is an object hierarchy that is applicable to arbitrary spatial objects that is formed by aggregating minimum bounding boxes for the spatial objects and storing the aggregates in a tree structure. The aggregation is based, in part, on proximity of the objects or bounding boxes. Each node in the tree represents a region in the space. Its children represent (possibly overlapping) subregions. The child regions do not need to cover the entire parent region. While the R−tree is designed primarily for storing region objects, it can be adapted to points by defining points as“degenerate” rectangles where all vertices are identical.
The number of objects or bounding boxes that are aggregated in each node is permitted to range between m≦(M/2) and M, thereby leading to use of the prefix (m, M) to characterize a particular R−tree and mirroring the effect of a B−tree. The root node in an R−tree has at least two entries unless it is a leaf node, in which case it has just one entry corresponding to the bounding box of an object. The tree is height-balanced (with maximum height logmr).
An R−tree can be constructed in either a dynamic or a static manner. Dynamic methods build the R−tree as the objects are encountered, while static methods wait until all the objects have been input before building the tree. The results of the static methods are usually characterized as being packed since knowing all of the data in advance permits each R−tree node to be filled to its capacity.
There are two principal methods of determining how to fill each R−tree node. The most natural method is to take the space occupied by the objects into account when deciding which ones to aggregate. An alternative is to order the objects prior to performing the aggregation. However, in this case, once an order has been established, there is not really a choice as to which objects (or bounding boxes) are being aggregated. One order preserves the order in which the objects were initially encountered. That is, the objects in aggregate i have been encountered before those in aggregate i+1.
According to one method, insertion of a region object R occurs as follows. Starting at root, children that completely contain R are identified. If no child completely contains R, one of the children is chosen and expanded so that it does contain R. If several children contain R, one is chosen and the process proceeds to the next child.
The above containment search is repeated with children of the current node. Once a leaf node is reached, R is inserted if there is room. If no room exists in the leaf, it is replaced by two leaves. Existing objects are partitioned between two leaves and parent. If no room exists in the parent, change propagates upward.
One difference between static and dynamic methods is that static methods rebuild the entire R−tree as each new object is added. In contrast, dynamic methods add the new objects to the existing R−tree. Dynamic methods differ in the techniques used to split an overflowing node during insertion.
There are two types of dynamic methods. The first type has the goal of minimizing coverage and overlap. These goals are at times contradictory and thus heuristics are often used. The second type makes use of the ordering applied to the objects (actually their bounding boxes). They are termed nonpacked. In this case, the result is equivalent to a B+−tree and all update algorithms are B+−tree algorithms. These update algorithms do not make use of the spatial extent of the bounding boxes to determine how to split a node. Thus, the goals of minimizing overlap or coverage are not part of the node splitting process although this does not preclude these methods from having good behavior with respect to these goals.
Static methods differ on the basis of the method used to order the objects. The dynamic methods that are not based on an ordering, that is, reduction of coverage and overlap, range from being quite simple, for example, exhaustive search, to being fairly complicated, for example, R*−tree. Some method just split the overflowing node, while others, that is, the R*−tree, try to reinsert some of the objects and nodes from the overflowing nodes thereby striving for better overall behavior (e.g., reduction in coverage and overlap).
In general, the goal of splitting techniques is to minimize coverage and overlap. These goals are at times contradictory and, thus, heuristics are often used. Below are listed a few node splitting algorithms that range from being quite simple, for example, exhaustive search, to being fairly complicated, for example, R*−tree. Some methods split the overflowing node, while others try to reinsert some of the objects and nodes from the overflowing nodes, thereby striving for better overall behavior, for example, reduction in coverage and overlap.
A number of different node splitting algorithms may be tried, including:                I. Dynamic Methods Based on Minimizing Coverage and/or Overlap                    1. Exhaustive search            2. Quadratic method            3. Linear method            4. R*−tree            5. Ang/Tan method                        II. Dynamic methods based on an ordering (nonpacked)                    1. Hilbert nonpacked            2. Morton nonpacked                        III. Static methods based on an ordering                    1. Packed            2. Hilbert packed            3. Morton packed            4. VAM split R−tree            5. Top-down-greedy split (TGS) R−treeMethods I and II are useful for insertion, while method III is typically used for “bulk” creation, that is, creation of indices on a given set of objects.                        